import java.util.PriorityQueue;

//数据流中的第 K 大元素
//测试链接：https://leetcode.cn/problems/kth-largest-element-in-a-stream/description/
public class KthLargest {
    PriorityQueue<Integer> pq;
    int max;
    public KthLargest(int k, int[] nums) {
        max = k;
        //创建小根堆
        pq = new PriorityQueue<>();  //Java默认为小根堆
        //数组元素放入堆
        for(int i = 0; i < nums.length; i++){
            if(i >= k){  //堆中已经放满K个元素
                if(pq.peek() < nums[i]){
                    pq.poll();
                    pq.add(nums[i]);
                }
            }else{
                pq.add(nums[i]);
            }
        }
    }

    public int add(int val) {
        if(pq.size() == max){
            if(pq.peek() < val){
                pq.poll();
                pq.add(val);
            }
        }else{
            pq.add(val);
        }

        return pq.peek();
    }
}
